The present invention relates to an address decoder for a memory.
Microprocessors and other integrated circuits store data in memory systems. The memory systems store digital data such as program instructions or variable data. Shown in FIG. 1, a typical memory system 100 includes an address decoder 110, a memory 120 and, optionally, a selection switch 130. The memory 120 is organized into rows, called "memory lines." Each memory line possesses a unique address. When an address is applied to the address decoder 110, the address decoder 110 causes data stored in the associated memory line to be output from the memory system 100.
In certain applications, it may be preferable to retrieve only part of a memory line. For example, a processor may load data into the memory 120 one memory line at a time but may use the loaded data in smaller increments. In this type of application, the selection switch 130 permits a selected portion of a memory line to be output from the memory system 100. An output to a common bus is applied to the selection switch. Thus, data from an enabled memory line is provided to the selection switch 130. The selection switch 130 selects a part of the memory line to be provided from the memory system 100.
To reference a desired portion of data in the form of signals, the address decoder 110 typically receives an address signal that identifies not only a requested memory line but also a portion of the memory line. The memory line is identified by a first part of the address (Addr.sub.s -Addr.sub.n); the portion of the memory line is identified by a second part of the address (Addr.sub.0 -Addr.sub.s-1).
The address decoder 110 is shown in greater detail in FIG. 2. The address decoder 110 is populated by a plurality of AND gates, one per memory line in memory 120. Each AND gate, such as gate 112, receives an input signals for each bit position of the first part of the address (Addr.sub.s -Addr.sub.n). Also for each bit position i, the address signals Addr.sub.i are inverted (Addr.sub.i #) so that either the true value of the address bit or its complement may be applied to an AND gate. For any AND gate, the gate is coupled to the one of Addr.sub.i or Addr.sub.i # that is a one when the appropriate address signal is applied.
For example, AND gate 112 should enable its memory line when address "0000" is applied to the address decoder. In response to "0000," Addr.sub.i =0 for all i. However, Addr.sub.i #=1 for all i. Therefore AND gate 112 receives input signals from Addr.sub.0 #, Addr.sub.i #, Addr.sub.2 #, etc. Similarly, AND gate 114 should enable its memory line when address "0001" is applied to the address decoder. Therefore, Addr.sub.i # is applied to AND gate 114 for all i.noteq.0. For address "0001," Addr.sub.0 =1 and is applied to the AND gate 114 instead of Addr.sub.0 #. Each AND gate is coupled to the address lines in accordance with the address to which the AND gate should be responsive.
It is a goal of memory systems to retrieve requested data as quickly as possible. Any delays that occur between the time that an address is posted and the time that the requested data is available for use are undesirable. At times, however, address data may be posted as one or more arithmetic operations. The arithmetic operations must be performed before an address may be applied to the address decoder 110. Traditional arithmetic operations are slow; they impose the undesired delay to data retrieval operations.
A traditional adder is shown in FIG. 3. There, four bit inputs X and Y are added together to obtain a four-bit sum S and a single bit carry C.sub.out. The adder includes an internal carry chain that propagates between every bit position in the adder. A carry from a first bit position may affect the value of the sum at a second bit position (S.sub.2). A carry from the second bit position may affect the value of the sum at a third bit position (S.sub.3). The carry chain continues through to the most significant bit. Because the carries affect the value of the sum result, true results cannot be output from the adder until the carry chain has traversed the entire length of the adder.
When several arithmetic operations are performed sequentially, carry chains must be completed for each operation. Sequential arithmetic operations on address data cause memory operations to be very slow.
Accordingly, there is a need in the art for a memory system that provides for fast retrieval of requested data when data is subject to arithmetic operations.
"Redundant form" adders are known to be faster than traditional adders. An example of a three input redundant form adder is shown in FIG. 4. There, the adder generates a multi-bit sum, labeled "S," from inputs W, X and Y. Each "bit position" in the resulting sum (such as S.sub.2) actually is represented by two bits. The redundant form adder does not possess the internal carry chain found in traditional adders. Accordingly, redundant form arithmetic operations are very fast relative to traditional arithmetic operations. To obtain a traditional, non-redundant result, the two bits at each bit position must be added together by a traditional adder. For example, the two bits of each sum position S.sub.i output by the redundant form adder may be input to the traditional adder of FIG. 3 to obtain a non-redundant result.
Traditional memory cannot operate on address data that is input in redundant form. No known memory system performs address decoding on address data in redundant form.